package com.example.demo.suanfa_quickSort;

import org.junit.Test;

import java.util.Stack;

/**
 * @program: java_base
 * @description: 快排
 * @author: zhouhongtao
 * @happyCreateTime: 2022/02/15 11:12
 */
public class QuickSortDemo {

    @Test
    public void quickSort1() {
        int[] arr = {1, 3, 4, 67, 89, 65, 3, 7, 8, 7, 99, 5, 43, 35};
        if (arr == null || arr.length < 2) {
            return;
        }
        int[] arr1 = {1, 3, 4, 67, 89, 65, 3, 7, 8, 7, 99, 5, 43, 35};
        quickSort(arr, 0, arr.length - 1);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(i+",");
        }
        System.out.println();
        quickSort_(arr1, 0, arr.length - 1);
        for (int i = 0; i < arr1.length; i++) {
            System.out.print(i+",");
        }
    }

    /**
     * 快排递归
     *
     * @param arr
     * @param l
     * @param r
     */
    private void quickSort(int[] arr, int l, int r) {
        // 若果左侧 比右侧大，则无法遍历，应该为不存在情况
        if (l >= r) {
            return;
        }
        swap(arr, (int) (Math.random() * (r - l + 1)), r);
        process3(arr, l, r);

    }

    /**
     * 荷兰国旗  smaller_value [a_index,b_index] bigger_value
     *
     * @param arr
     * @param l
     * @param r
     * @return copy from zuochengyun
     */
    private void process3(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
        int[] equalArea = netherlandsFlag(arr, l, r);
        process3(arr, l, equalArea[0]);
        process3(arr, equalArea[1], r);
    }

    // arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值
    // <arr[R] ==arr[R] > arr[R]
    // 返回两个索引   荷兰国旗  smaller_value [a_index,b_index] bigger_value
    private int[] netherlandsFlag(int[] arr, int l, int r) {
        if (l > r) {
            // L...R L>R
            return new int[]{-1, -1};
        }
        if (l == r) {
            return new int[]{l, r};
        }
        // 边界 和 遍历指针
        // 边界
        int less = l - 1; // < 区 右边界
        int more = r; // > 区 左边界
        // 遍历指针
        int index = l;
        // 当前位置，不能和 >区的左边界撞上
        while (index < more) {
            // 用范围内最后一个数作为  划分区域的锚定值
            if (arr[index] == arr[r]) {
                index++;
            } else if (arr[index] < arr[r]) {
//				swap(arr, less + 1, index);
//				less++;
//				index++;
                swap(arr, index++, ++less);
            } else { // >
                swap(arr, index, more--);
            }
        }
        // 最后还需要交换下 r位置元素，和 more边界值交换
        swap(arr, more, r);
        return new int[]{less, more};
    }


    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 快排非递归方式

    /**
     * 使用栈结构，替代系统栈
     *
     * @param arr 数组
     * @param l   index
     * @param r   index
     */
    public void quickSort_(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
        int[] equalArea = netherlandsFlag(arr, l, r);

        int el = equalArea[0];
        int er = equalArea[1];

        Stack<Op> stack = new Stack();
        stack.push(new Op(l, el - 1));
        stack.push(new Op(er + 1, r));
        while (!stack.isEmpty()) {
            // op.l ... op.r
            Op op = stack.pop();
            if (op.l < op.r) {
                swap(arr, op.l + (int) (Math.random() * (op.r - op.l + 1)), op.r);
                equalArea = netherlandsFlag(arr, op.l, op.r);
                stack.push(new Op(op.l, equalArea[0] - 1));
                stack.push(new Op(equalArea[1] + 1, op.r));
            }
        }

    }

    class Op {
        int l;
        int r;
        // 快排非递归版本需要的辅助类
        // 要处理的是什么范围上的排序
        public Op(int left, int right) {
            l = left;
            r = right;
        }
    }

}
